home *** CD-ROM | disk | FTP | other *** search
/ CD ROM Paradise Collection 4 / CD ROM Paradise Collection 4 1995 Nov.iso / arcers / tar316.zip / MATCH.ASM < prev    next >
Assembly Source File  |  1980-07-24  |  7KB  |  195 lines
  1. ; The following sorce code is derived from Info-Zip 'zip' 2.01
  2. ; distribution copyrighted by Mark Adler, Richard B. Wales,
  3. ; Jean-loup Gailly, Kai Uwe Rommel, Igor Mandrichenko and John Bush.
  4.  
  5. ; match.asm is initially written by Jean-loup Gailly.
  6.  
  7. ; match.asm, optimized version of longest_match() in deflate.c
  8. ; Must be assembled with masm -ml. To be used only with C large or
  9. ; compact model. (For compact model, assemble with -D__NEAR__).
  10. ; This file is only optional. If you don't have masm or tasm, use the
  11. ; C version.
  12. ; If you have reduced WSIZE in zip.h, then change its value below.
  13. ;
  14. ; For the C compilers, which allows static allocation of more than 64K
  15. ; bytes per file, it's possible to simplify code by using -DST_ALLOC
  16. ; compilation option.
  17. ;
  18. ; To simplify the code, dynamically allocated arrays must have zero
  19. ; offset (allocated by halloc).
  20.  
  21.         include farnear.inc
  22.  
  23. ifdef ST_ALLOC
  24.         extrn   _prev         : word
  25.         extrn   _window       : byte
  26.         prev    equ  _prev    ; offset part
  27.         window  equ  _window
  28. endif
  29.  
  30. _DATA   segment  word public 'DATA'
  31. ifndef ST_ALLOC
  32.         extrn   _prev         : word
  33.         extrn   _window       : word
  34.         prev    equ 0         ; offset forced to zero
  35.         window  equ 0
  36.         window_seg equ _window[2]
  37.         window_off equ 0
  38.         prev_seg   equ _prev[2]
  39. else
  40.         window_seg dw  seg _window
  41.         window_off equ offset _window
  42.         prev_seg   dw  seg _prev     ; pointer to the prev array
  43. endif
  44.         extrn   _nice_match   : word
  45.         extrn   _match_start  : word
  46.         extrn   _prev_length  : word
  47.         extrn   _good_match   : word
  48.         extrn   _strstart     : word
  49.         extrn   _max_chain_length : word
  50. _DATA   ends
  51.  
  52. DGROUP  group _DATA
  53.  
  54. _TEXT   segment word public 'CODE'
  55.         assume  cs: _TEXT, ds: DGROUP
  56.  
  57.         MIN_MATCH     equ 3
  58.         MAX_MATCH     equ 258
  59.         WSIZE         equ 32768         ; keep in sync with zip.h !
  60.         MIN_LOOKAHEAD equ (MAX_MATCH+MIN_MATCH+1)
  61.         MAX_DIST      equ (WSIZE-MIN_LOOKAHEAD)
  62.  
  63. ; initialize or check the variables used in match.asm.
  64.  
  65.         program _match_init
  66. ifndef ST_ALLOC
  67.         mov     ax,_prev[0]
  68.         or      ax,_window[0]   ; verify zero offset(s) - both in a turn
  69. else
  70.         xor     ax,ax
  71. endif
  72.         ret
  73. _match_init endp
  74.  
  75. ; Set match_start to the longest match starting at the given string and
  76. ; return its length. Matches shorter or equal to prev_length are discarded,
  77. ; in which case the result is equal to prev_length and match_start is
  78. ; garbage.
  79. ; IN assertions: cur_match is the head of the hash chain for the current
  80. ;   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  81.  
  82. ; int longest_match(cur_match)
  83.  
  84.         program _longest_match
  85.  
  86.         push    bp
  87.         mov     bp,sp
  88.         push    di
  89.         push    si
  90.         push    ds
  91.  
  92. ifdef __FAR__
  93.         cur_match    equ word ptr [bp+6] ; [bp+6] for large model
  94. else
  95.         cur_match    equ word ptr [bp+4] ; [bp+4] for compact model
  96. endif
  97.  
  98. ;       window       equ es:0 (es:window for ST_ALLOC)
  99. ;       prev         equ ds:prev
  100. ;       match        equ es:si
  101. ;       scan         equ es:di
  102. ;       chain_length equ bp
  103. ;       best_len     equ bx
  104. ;       limit        equ dx
  105.  
  106.         mov     si,arglist[0]   ; = cur_match (use bp before it is destroyed)
  107.         mov     bp,_max_chain_length    ; chain_length = max_chain_length
  108.         mov     di,_strstart
  109.         mov     dx,di
  110.         sub     dx,MAX_DIST             ; limit = strstart-MAX_DIST
  111.         jae     limit_ok
  112.         sub     dx,dx                   ; limit = NIL
  113. limit_ok:
  114.         add     di,2+window_off         ; di = offset(window + strstart + 2)
  115.         mov     bx,_prev_length         ; best_len = prev_length
  116.         mov     es,window_seg
  117.         mov     ax,es:[bx+di-3]         ; ax = scan[best_len-1..best_len]
  118.         mov     cx,es:[di-2]            ; cx = scan[0..1]
  119.         cmp     bx,_good_match          ; do we have a good match already?
  120. ; Note: DS still points to static data (DGROUP)
  121.         mov     ds,prev_seg             ; (does not destroy the flags)
  122.         jb      do_scan                 ; good match?
  123.         shr     bp,1                    ; chain_length >>= 2
  124.         shr     bp,1
  125.         jmp     short do_scan
  126.  
  127.         even                            ; align destination of branch
  128. long_loop:
  129. ; at this point, es:di == scan+2, es:si == cur_match
  130.         mov     ax,es:[bx+di-3]         ; ax = scan[best_len-1..best_len]
  131.         mov     cx,es:[di-2]            ; cx = scan[0..1]
  132. ; Note: DS always points to static data here
  133.         mov     ds,prev_seg             ; reset ds to address the prev array
  134.         assume  ds: nothing
  135. short_loop:
  136. ; at this point, di == scan+2, si = cur_match,
  137. ; ax = scan[best_len-1..best_len] and cx = scan[0..1]
  138. if (WSIZE-32768)
  139.         and     si,WSIZE-1              ; not needed if WSIZE=32768
  140. endif
  141.         shl     si,1                    ; cur_match as word index
  142.         mov     si,prev[si]             ; cur_match = prev[cur_match]
  143.         cmp     si,dx                   ; cur_match <= limit ?
  144.         jbe     the_end
  145.         dec     bp                      ; --chain_length
  146.         jz      the_end
  147. do_scan:
  148.         cmp     ax,word ptr es:window[bx+si-1] ; check match at best_len-1
  149.         jne     short_loop
  150.         cmp     cx,word ptr es:window[si]      ; check min_match_length match
  151.         jne     short_loop
  152.  
  153.         lea     si,window[si+2]         ; si = match
  154.         mov     ax,di                   ; ax = scan+2
  155.         mov     cx,es
  156.         mov     ds,cx                   ; ds = es = window
  157.         mov     cx,(MAX_MATCH-2)/2      ; scan for at most MAX_MATCH bytes
  158.         repe    cmpsw                   ; loop until mismatch
  159.         je      maxmatch                ; match of length MAX_MATCH?
  160. mismatch:
  161.         mov     cl,[di-2]               ; mismatch on first or second byte?
  162.         sub     cl,[si-2]               ; cl = 0 if first bytes equal
  163.         xchg    ax,di                   ; di = scan+2, ax = end of scan
  164.         sub     ax,di                   ; ax = len
  165.         sub     si,ax                   ; si = cur_match + 2 + offset(window)
  166.         sub     si,2+window_off         ; si = cur_match
  167.         sub     cl,1                    ; set carry if cl == 0 (can't use DEC)
  168.         adc     ax,0                    ; ax = carry ? len+1 : len
  169.         pop     ds                      ; DS now points to static data
  170.         assume  ds: DGROUP
  171.         push    ds                      ; restore stack
  172.         cmp     ax,bx                   ; len > best_len ?
  173.         jle     long_loop
  174.         mov     _match_start,si         ; match_start = cur_match
  175.         mov     bx,ax                   ; bx = best_len = len
  176.         cmp     ax,_nice_match          ; len >= nice_match ?
  177.         jl      long_loop
  178. the_end:
  179.         pop     ds
  180.         pop     si
  181.         pop     di
  182.         pop     bp
  183.         mov     ax,bx                   ; result = ax = best_len
  184.         ret
  185.  
  186.         even
  187. maxmatch:                               ; come here if maximum match
  188.         cmpsb                           ; increment si and di
  189.         jmp     mismatch                ; force match_length = MAX_LENGTH
  190.  
  191. _longest_match  endp
  192.  
  193. _TEXT   ends
  194. end
  195.